package _10_binary_tree.order.scope;

import _04_queue.my_implements.ArrayQueue;
import org.junit.Test;

import java.util.*;

/**
 * @author: mornd
 * @dateTime: 2023/6/7 - 23:46
 * 二叉树Z型遍历 奇数从左向右，偶数从右向左，非层序遍历
 *
 *          1
 *         /\
 *        2  3
 *       /\ /\
 *      4 5 6 7
 *     /\
 *    8 9
 *
 *    遍历得到的结果是：1,3,2,4,5,6,7,9,8
 */
public class ZigzagLevelOrderTest {
    @Test
    public void test() {
        // 构建树节点
        TreeNode root = new TreeNode(1,
                new TreeNode(2,
                        new TreeNode(4,
                                new TreeNode(8), new TreeNode(9)),
                        new TreeNode(5)),
                new TreeNode(3,
                        new TreeNode(6),
                        new TreeNode(7)));

        List<Deque<Integer>> list = func(root);
        list.forEach(System.out::println);
    }

    List<Deque<Integer>> func(TreeNode treeNode) {
        ArrayQueue<TreeNode> queue = new ArrayQueue<>(10);
        queue.offer(treeNode);

        int i = 1;
        boolean odd = true;
        List<Deque<Integer>> outerList = new ArrayList<>();
        while (!queue.isEmpty()) {
            int j = 0;
            // 此时的 LinkedList 代表双端队列
            Deque<Integer> innerList = new LinkedList<>();
            for (int k = 0; k < i; k++) {
                TreeNode n = queue.poll();
                if (odd) {
                    // 奇数从左往右添加
                    innerList.addLast(n.val);
                } else {
                    // 偶数从右往左添加
                    innerList.addFirst(n.val);
                }
                if (n.left != null) {
                    queue.offer(n.left);
                    j++;
                }
                if (n.right != null) {
                    queue.offer(n.right);
                    j++;
                }
            }
            i = j;
            odd = !odd;

            outerList.add(innerList);
        }
        return outerList;
    }
}
